package j20251114;

public class Solution1 {
    public int lengthOfLIS(int[] nums) {
        int ret=0;
        int n=nums.length;
        int[] memo=new int[n];
        for(int i=0;i<n;i++){
            ret=Math.max(ret,dfs(i,nums,memo));
        }
        return ret;
    }
    public int dfs(int pos,int[] nums,int[] memo){
        if(memo[pos]!=0) return memo[pos];
        int ret=1;
        for(int i=pos+1;i<nums.length;i++){
            if(nums[pos]<nums[i]){
                ret=Math.max(ret,dfs(i,nums,memo)+1);
            }
        }
        memo[pos]=ret;
        return ret;
    }
}
